More and more systems are relying upon read-only data bases that store information for use by electronic computers. As used herein, a read-only data base is one that is not constructed to permit the user to alter the data base. Typical data processing systems that rely upon read-only data bases are program data for personal computer programs, data for dedicated processing computers, on-line data base systems, commercial text retrieval systems, etc. The data, or information, stored by these systems typically includes a large number of data words, wherein each data word includes a plurality of binary data bits.
A common problem associated with storing the data words of a read only data base is the amount of overhead storage space required. As used herein, "storage space" refers to any space where the data words are stored and "overhead storage" space refers to that portion of the storage space required to store a data word that does not include data bits of the data word. As an example of overhead storage space, data processing systems that store a data base typically define in advance how many data bits will be associated with each data word of the stored information. The defined number of data bits are referred to herein as the predetermined number of data bits. The predetermined number of data bits to be associated with each data word is usually selected to accommodate the largest expected data word to be stored. Consequently, data words having less than the maximum number of expected data bits will also be stored using the predetermined number of data bits. The difference between the number of bits required to store the smaller data words and the predetermined number of data bits represents overhead storage. It is desirable, therefore, to provide a method for storing digital data that does not require unused data bits, or overhead, to store the smaller data words.
Several methods have been proposed for storing a data base without providing a predetermined number of data bits for each data word. However, these methods typically require additional bits to be associated and stored with each data word to describe to the data processing system reading the information the number of data bits in the associated data word. Although these systems have proven acceptable for some forms of data bases, these methods are not acceptable for a data base wherein the number of data bits required to store each data word falls within a limited range. This is because when the number of data bits required to store each data word falls within a limited range, the overhead associated with describing the number of data bits in each data word becomes unduly burdensome and detracts from the performance of these systems. Accordingly, it is desirable to provide a method of storing a data base without providing a predetermined number of data bits for each data word, and wherein the amount of overhead necessary to store each data word can be minimized.